The present invention relates in general to raster-based image generation and in particular to systems and methods for dithering of image data based on error accumulation.
Modern graphics processing systems generate pixel data at high color resolution. For instance, a color resolution of 24 bits (8 bits in each red, green, and blue color component) is commonly used. In some cases, the color resolution available in the graphics processing system can exceed the color resolution available (or in use) on a particular display device. For example, some LCD devices use 18-bit color (6 bits in each color component), making fewer colors available.
Color dithering is often used to create the appearance of a larger number of colors than a given display device provides. For instance, if a region within the image is to be displayed at a color intermediate in intensity between two available colors, the appearance of the intermediate color can be created by displaying some of the pixels at the lower intensity color and some at the higher intensity color. For example, suppose that some area of an image is supposed to have a color (or color component) C0 whose intensity is intermediate between a lower available value CL and a higher available value CH. For an N*N block of pixels, there is an integer “mixing factor” P that most nearly satisfies the equation:C0=CH*P/N2+CL*(N2−P)/N2.The desired color C0 can be approximated by setting the color value for P of the N*N pixels to the higher value CH, and the color value for the rest of the pixels to the lower value CL. The selection of which P pixels to set to the higher value CH is often made by applying an N*N “dither matrix” to each pixel block on the screen. The entries in the dither matrix, each corresponding to a different pixel, typically consist of the numbers from 0 to N2−1, arranged in a pattern such that the desired color effect is produced by setting the color to CH for pixels whose dither matrix entry is less than P and to CL for the remaining pixels. The dither matrix is repeated for each N*N block of pixels in the display, with a typical value of N being 4. This dithering procedure is usually applied separately to each color component.
Matrix-based dithering, however, can produce undesirable artifacts in the displayed image. For example, due to the repetition of the dither matrix for each block of pixels, a visible “screen door” effect can occur as similar patterns of bright and dark pixels tend to recur in horizontal and vertical bands across the image. Some implementations attempt to avoid this by rearranging the entries in the dither matrix on successive frames (e.g., in a 4-frame cycle for a 4×4 dither matrix), thereby blurring the temporal resolution. However, the cycle is often slow enough to produce visible scintillation or flickering effects.
As an alternative to a fixed dither matrix, Floyd and Steinberg have proposed a dithering algorithm based on error forwarding from pixels earlier in the scanout order to later scanned neighbors. This algorithm is illustrated in FIG. 1 for a 3×3 block of pixels 100. Pixels 110-118 are scanned in raster order (across rows, starting at the top). The display color (CD) of pixel 114 is determined based on the desired color for that pixel (C0) plus an error term ε accumulated from respective error terms ε0 to ε3 of previously scanned neighbor pixels 110-113. For example, if C0+ε≧CH, then CH is chosen as the displayed color CD, otherwise CL is chosen. A residual error ε4 (e.g., C0-CD) is then determined and forwarded to the unscanned neighbor pixels 115-118 as shown. The forwarded error is distributed unequally among the unscanned neighbors; e.g., 7/16 of ε4 is forwarded to pixel 115, while only 1/16 of ε4 is forwarded to pixel 116. The same distribution pattern is used for each pixel. Because each pixel is a neighbor of several others, the error for a given pixel is the sum of errors from previously scanned neighbors. For example, the error term ε used to determine the color of pixel 114 would be:ε=( 3/16)*ε0+( 5/16)*ε1+( 1/16)*ε2+( 7/16)*ε3,where ε0 to ε3 are the respective residual errors for pixels 110-113. As with matrix-based dithering, R, G, and B color components can be processed independently using this procedure. This technique results in a distribution of higher-intensity (CH) pixels among lower-intensity (CL) pixels to produce the desired visual effect, and the error distribution introduces quasi-random variation that can reduce or eliminate the undesired screen door effect.
Such an error distribution algorithm, however, is expensive to implement in hardware. For instance, a line store is generally needed to keep track of errors to be added to each pixel in the next row while processing a current row, and frequent read-modify-write operations on the line store are required to accumulate the errors from all neighbor pixels.
It would therefore be desirable to provide a dithering technique that avoids screen door effects or other visual artifacts while still being inexpensive to implement.